package code;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class Substring {
    public int lengthOfLongestSubstring(String s) {
    	int i,j;
    	int n=s.length();
    	int ans=0;
    	/*
    	 * ����c[i],��i�Ķ�Ӧ��ϵ
    	 */
    	Map<Character,Integer> map=new HashMap<Character,Integer>();
    	int maxLen=0;
    	for(i=0;i<n;i++){
    		if(map.containsKey(s.charAt(i))){
    			int startIdx=map.get(s.charAt(i));
    			/*
    			 * ��s[i]��֮ǰ��Ԫ��ȫ��ɾ��
    			 */
    			for(j=i-maxLen;j<startIdx;j++)
    				map.remove(s.charAt(j));
    			
    			maxLen=i-startIdx;
    			map.put(s.charAt(i), i);

    		}
    		else{
    			map.put(s.charAt(i), i);
    			maxLen++;
    		}
    		if(maxLen>ans) ans=maxLen;
    	}
        return ans;
    }
    
    public String longestCommonPrefix(String[] strs) {
    	int i,j;
    	int n=strs.length;
    	for(i=strs[0].length();i>0;i--){
    		String sub=strs[0].substring(0, i);
    		for(j=1;j<n;j++){
    			if(i>strs[j].length() || !strs[j].subSequence(0, i).equals(sub))
    				break;
    		}
    		if(j==n){
    			return sub;
    		}
    	}
    	return null;
    }
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
    
    public boolean isOk(String s){
    	Stack<Character> stack=new Stack<Character>();
    	for(int i=0;i<s.length();i++){
    		char c=s.charAt(i);
    		if(c=='('){
    			stack.push(c);
    		}
    		else{
    			if(stack.empty()){
    				return false;
    			}
    			else{
    				stack.pop();
    			}
    		}
    	}
    	if(stack.isEmpty())	return true;
    	return false;
    }
    
    public int longestValidParenthesesII(String s) {
        
    	int i,j;
    	int ans=0;
    	for(i=0;i<s.length();i++){
    		for(j=s.length()-1;j>i;j--){
    			if((j-i+1)%2!=0)
    				continue;
    			if(isOk(s.substring(i,j+1))){
    				ans=j-i+1;
    				return ans;
    			}
    		}
    	}
    	return ans;
    }
    /*
     * ���Ƶ�˼�룺
     * dp[i]��ʾi���ġ�������dp[i]�ġ�����ƥ����
     * dp[i+1]=dp[i]-1��i+1�Ƚϣ����ܲ��ܳɹ�
     * ���и�õ�����
     * ���ǵ�һ������
     * stack��ģ�⣬���ÿ�������Ƿ�ƥ�䣬Ȼ��ö��������Ķ�
     * 
     */
    public int longestValidParentheses(String s){
    	int ans=0;
    	int n=s.length();
    	int i,j;
    	boolean[] isMatch=new boolean[n];
    	Stack<Integer> stack=new Stack<Integer>();
    	
    	for(i=0;i<n;i++){
    		char c=s.charAt(i);
    		if(c=='('){
    			stack.push(i);
    		}
    		else{
    			if(!stack.empty()){
    				isMatch[i]=true;
    				isMatch[stack.pop()]=true;
    			}
    		}
    	}
    	
    	for(i=0;i<n;){
    		if(!isMatch[i]){
    			i++;
    		}
    		else{
	    		j=i;
	    		while(j<n && isMatch[j])
	    			j++;
	    		if(ans<j-i)
	    			ans=j-i;
	    		i=j;
    		}
    	}
    	return ans;
    }
    public static void main(String[] args){
    	System.out.println(new Substring().longestValidParentheses("(()())"));
    }
}
